package com.chj.chuji.tijie14;

//https://blog.csdn.net/m0_37579232/article/details/81259629
//https://ac.nowcoder.com/acm/contest/156
//https://blog.csdn.net/deaidai/article/details/78167367
//https://blog.csdn.net/Jasmineaha/article/details/81415272
//https://blog.csdn.net/qq_42166308/article/details/103980076
//https://www.cnblogs.com/cjjsb/p/9832588.html#c-%E6%89%98%E7%B1%B3%E7%9A%84%E4%BD%8D%E8%BF%90%E7%AE%97
public class BitOperation02 {
	public static void main(String[] args) {

		System.out.println(1 << 3);
		System.out.println(Integer.toBinaryString(1 << 3));
		System.out.println(1 << 4);
		System.out.println(Integer.toBinaryString(1 << 4));
		System.out.println((1 << 3) - 1);
		System.out.println(Integer.toBinaryString((1 << 3) - 1));
		System.out.println((1 << 4) - 1);
		System.out.println(Integer.toBinaryString((1 << 4) - 1));
		System.out.println();
		System.out.println(Integer.toBinaryString(4));
		System.out.println(Integer.toBinaryString(5));
		System.out.println((4 >> 2));
		System.out.println((5 >> 2));
		System.out.println(4 & 5);
		System.out.println(4 & 4);
		System.out.println(4 & 6);
		System.out.println(4 & 7);
		System.out.println(Integer.toBinaryString(8));
		System.out.println(4 & 8);
		System.out.println(Integer.toBinaryString(9));
		System.out.println(4 & 9);
		int n = 5;
		int res = 0;
		int[] ard = new int[] { 1, 2, 3, 4, 5 };
		int[] a = new int[n + 1];
		int[] ans = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = ard[i - 1];
		}

		for (int v = 30; v >= 0; v--) {// 从高位开始枚举
			int p = 1 << v; // 判断当前最高位i是否为1
			int temp = p - 1; // 判断除最高位外其余位是否为0
//			int temp = (1 << v) - 1;//1 << i; //判断当前最高位i是否为1;
			res = 0;
			for (int i = 1; i <= n; i++) {
				if (a[i] == 4) {
					System.out.println("v: " + v);
				}

				if (((a[i] >> v) & 1) == 1) {
					System.out.println("temp: " + temp);
					System.out.println("a[i]: " + a[i]);
					temp = (temp & a[i]);
					ans[res++] = i;
					System.out.println("22temp: " + temp);
				}
			}
			if (temp == 0) {
//				printf("%d\n",res);
				System.out.println("res: " + res);
				for (int i = 0; i < res; i++) {
//					printf("%d%c",a[ans[i]],i==res-1?'\n':' ');
					System.out.print(a[ans[i]] + " ");
					if (i == res - 1) {
						System.out.println();
					}
				}

				break;
			}
		}
	}
}

/*
 * 题目大意：（中文题目，不解释了） 这题主要是技巧， 一个是如何判断一个数是（1<<i）的呢？ 需要用到树状数组里面的lowbit知识，
 * 有了这个判定就方便多了 比赛时这题搞烦了，主要是对时间复杂度的不敏感 还特地用节点存储排了序，导致好多错误。。。。 仔细想想暴力一点就10^6的复杂度。
 * 下面讨论里面的数学。 对于i位开头是1的所有数， 如果这些数中有任意两个相与其结果为(1<<i）
 * 那么贪心可得，这个范围的数都可以选，但不能比这个小的任何数。 那么倒退i，让1<<i的范围倒退即可，逐步判断，一旦发现了一定是最佳的选择
 */
